Chứng minh gồm hai phần. Phần một chứng minh mọi số có thể viết dưới dạng tích của một hoặc nhiều số nguyên tố. Phần thứ hai chứng tỏ rằng biểu diễn đó là duy nhất.

Phân tích các số

Trước hết, mỗi số nguyên tố là tích của một thừa số là chính nó. Giả sử rằng có các số nguyên dương lớn hơn 1 không biểu diễn được thành tích các số nguyên tố. Khi đó gọi n là số nhỏ nhất trong các số đó. Số n này khác 1 và là hợp số. Do đó

trong đó cả a và b là các số nguyên dương nhỏ hơn n. Vì n là số nhỏ nhất không thể phân tích thành tích các số nguyên tố nên cả a và b phân tích được thành tích các số nguyên tố. Nhưng khi đó

lại phân tích được. Điều này mâu thuẫn với giả thiết.

Chứng minh cách biểu diễn là duy nhất

Ta giả sử rằng tồn tại số nguyên lớn hơn 1 mà có 2 cách biểu diễn dưới dạng tích các thừa số nguyên tố. Khi đó giả sử s là số nhỏ nhất trong các số như vậy, tức là s = p 1 p 2 . . . p m = q 1 q 2 . . . q n {\displaystyle s=p_{1}p_{2}...p_{m}=q_{1}q_{2}...q_{n}} với p i , q j {\displaystyle p_{i},q_{j}} là các số nguyên tố. Do p 1 {\displaystyle p_{1}} chia hết q 1 q 2 . . . q n {\displaystyle q_{1}q_{2}...q_{n}} suy ra tồn tại q j {\displaystyle q_{j}} mà p 1 {\displaystyle p_{1}} chia hết q j {\displaystyle q_{j}} . Từ đó ta có p i = q j {\displaystyle p_{i}=q_{j}} , bỏ 2 số nguyên tố ra khỏi đẳng thức ta được 2 vế là 2 khai triển khác nhau của số s chia cho p 1 {\displaystyle p_{1}} , mà theo giả thuyết s là số nhỏ nhất như vậy, mâu thuẫn này chứng tỏ giả thiết là sai. vậy mỗi số nguyên lớn hơn một chỉ có một biểu diễn duy nhất dưới dạng tích thừa số nguyên tố (không kể đến thứ tự các thừa số).